//
//  KMP字符串匹配.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/6.
//

import UIKit

class KMPStringPattern: NSObject {
    func QA() {
        print(indexOf("Hello World", "H") == 0)
        print(indexOf("Hello World", "or") == 7)
        print(indexOf("Hello World", "abc") == -1)

    }
    func indexOf(_ text: String, _ pattern: String) -> Int {
        if text.count == 0 || pattern.count == 0 || text.count < pattern.count {
            return -1
        }
        let tArray = Array(text)
        let pArray = Array(pattern)
        let tlen = tArray.count
        let plen = pArray.count
        let nexts = getNextArray(pArray)
        var pi = 0
        var ti = 0
        while pi < plen && ti-pi <=  tlen - plen {
            if tArray[ti] == pArray[pi] {
                pi += 1
                ti += 1
            } else {
                if nexts[pi] < 0 { // 首字母匹配失败的情况
                    pi = 0
                    ti += 1
                } else {
                    pi = nexts[pi]
                }
            }
        }
        if pi == plen {
            return ti - pi
        } else {
            return -1
        }
    }
    
    func getNextArray(_ pattern: [Character]) -> [Int] {
        var nexts = Array(repeating: 0, count: pattern.count)
        nexts[0] = -1
        var n = -1
        let imax = pattern.count - 1
        var i = 0
        while i < imax {
            if n < 0 || pattern[i] == pattern[n] {
                i += 1
                n += 1
                nexts[i] = n
            } else {
                n = nexts[n]
            }
        }
        return nexts
    }
}
